package com.wfm.niuke.beibao;

import org.junit.Test;

/**
 * 	   重量	价值
 * 物品0	1	15
 * 物品1	3	20
 * 物品2	4	30
 *
 *
 */
public class P01package {
    int package01(int[] weight,int[] value,int n){
        int m = weight.length;
        int[][] dp = new int[m][n+1];
        // 初始化第一行
        for (int j = weight[0]; j <= n; j++) {
            dp[0][j] = value[0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j <= n; j++) {
                if(j<weight[i]){ // 背包装不下
                    dp[i][j]=dp[i-1][j];
                }else {  // 背包装得下，选择装或者不装的最大
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }
        return dp[m-1][n];
    }
    @Test
    public void test(){
        int[] w = new int[]{1,5,11,5};
        int[] v = new int[]{1,5,11,5};
        int n = 11;
        int i = package01(w, v, n);
        System.out.println(i);
    }
}
